package _11_整理题目._4_动态规划._子数组子矩阵;

import org.junit.Test;

/**
 * 给定一个数组 nums，返回连续子数组的最大和
 * 例如，arr = [1, -2, 3, 5, -2, 6, -1]，
 * 所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
 * 题目保证没有全为负数的数据
 * 
 * 动态规划模板：
 * 1、定义 dp[] 中 dp[i] 的意思，初始化 dp 长度
 *      dp[i] 表示 前 i 个数组元素（下标 0 到 下标 i 中某个连续子数组的最大和）
 * 2、确定边界值，即最初值 dp[0]= arr[0];
 * 3、确定状态转移方程，即 dp[i] 和 dp[i-1] 的关系
 *      如果 dp[i-1] > 0，则加入到 nums[i]：即取 nums[i] 和 nums[i]+dp[i-1] 的较大值
 *      每次求出 dp[i] 后，更新最大值
 * 
 * 为了节省空间，可以使用原数组作为 dp 数组
 * 
 */
public class _01_连续子数组最大和 {

    // 新建 dp，时间 O(n)，空间 O(n)
    public int maxSumOfSubarray0(int[] nums) {
        int n = nums.length;
        int dp[] = new int[n];
        dp[0] = nums[0];
        int max = dp[0];
        for(int i = 1; i < n; i++) {
            if(dp[i-1] > 0) {
                dp[i] = dp[i-1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    // 新建 dp，时间 O(n)，空间 O(n)，
    // 换一种写法，将求 dp 和求 max 分开计算
    public int maxSumOfSubarray1(int[] nums) {
        int n = nums.length;
        int dp[] = new int[n];
        System.arraycopy(nums, 0, dp, 0, n);
        for(int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
        }
        int max = dp[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(dp[i],max);
        }
        return max;
    }

    // 使用原数组 时间 O(n)，空间 O(1)
    public int maxSumOfSubarray2(int[] nums) {
        int n = nums.length;
        int max = nums[0];
        for(int i = 1; i < n; i++) {
            nums[i] = Math.max(nums[i], nums[i-1]+nums[i]);
            max = Math.max(max, nums[i]);
        }
        return max;
    }
    
    @Test
    public void main() {
        int[] nums = {1, -2, 3, 5, -2, 6, -1};
        System.out.println(maxSumOfSubarray0(nums));
        System.out.println(maxSumOfSubarray1(nums));
        System.out.println(maxSumOfSubarray2(nums));
    }
    
}
